package com.zhengb.algorithmdemo.leetcode.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
 * 二叉树前序遍历
 *
 * @author zhengbo
 * @date 2020/3/25
 */
public class PreOrderTraverseTree {

    private void preOrderTraverseRecursive(TreeNode rootNode, List<Integer> list) {

        if (rootNode != null) {
            list.add(rootNode.val);
            preOrderTraverseRecursive(rootNode.left, list);
            preOrderTraverseRecursive(rootNode.right, list);
        }
    }

    private List<Integer> preOrderTraverseNoRecursive(TreeNode rootNode) {

        if (rootNode == null) {
            return Collections.emptyList();
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode tempNode = rootNode;

        List<Integer> resultList = new ArrayList<>();
        while (true) {
            while (tempNode != null) {
                resultList.add(tempNode.val);
                stack.push(tempNode);
                tempNode = tempNode.left;
            }
            if (stack.isEmpty()) {
                break;
            }
            tempNode = stack.pop().right;
        }

        return resultList;
    }

    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> resultList = new ArrayList<>();
        preOrderTraverseRecursive(root, resultList);

        return resultList;
    }

    public static void main(String[] args) {
        TreeNode one = new TreeNode(1);
        TreeNode two = new TreeNode(2);
        TreeNode three = new TreeNode(3);
        TreeNode four = new TreeNode(4);
        TreeNode five = new TreeNode(5);
        TreeNode six = new TreeNode(6);
        TreeNode seven = new TreeNode(7);
        TreeNode eight = new TreeNode(8);

        one.left = two;
        one.right = three;


        two.left = four;
        two.right = five;

        three.left = six;
        three.right = seven;

        four.right = eight;

        PreOrderTraverseTree preOrderTraverseTree = new PreOrderTraverseTree();
        List<Integer> list = preOrderTraverseTree.preOrderTraverseNoRecursive(one);

        System.out.println(list);

        list.clear();
        preOrderTraverseTree.preOrderTraverseRecursive(one, list);
        System.out.println(list);

    }
}
